/*
Implement sparse matrix addition using an efficient data structure.

Program by Thomas Jacob (4036) and Syam Kumar (4035)
January 15,2001
*/

#include<stdio.h>
#include<conio.h>

 int i,j,r,c,input;
 int sparse_a[25][3],sparse_b[25][3];
 int sum[5][5];
 int atop=0,btop=0;

void main()
{

 clrscr();
 printf("Enter no. of rows and columns of the matrix : ");
 scanf("%d %d",&r,&c);

 printf("\nEnter the first matrix.\n");
 for(i=0;i<r;i++)
  for(j=0;j<c;j++)
   {
    scanf("%d",&input);
    if(input!=0)
     {
      sparse_a[atop][0]=i;
      sparse_a[atop][1]=j;
      sparse_a[atop][2]=input;
      atop++;
     }
   } atop--;

 printf("\nEnter the second matrix.\n");
 for(i=0;i<r;i++)
  for(j=0;j<c;j++)
   {
    scanf("%d",&input);
    if(input!=0)
     {
      sparse_b[btop][0]=i;
      sparse_b[btop][1]=j;
      sparse_b[btop][2]=input;
      btop++;
     }
   } btop--;


  /*Initialise sum matrix*/
  for(i=0;i<r;i++)
   for(j=0;j<c;j++)
     sum[i][j]=0;

  /*Add the non-zero values*/
  for(i=0;i<=atop;i++)
    sum [sparse_a[i][0]][sparse_a[i][1]] += sparse_a[i][2];
  for(i=0;i<=btop;i++)
    sum[sparse_b[i][0]][sparse_b[i][1]] += sparse_b[i][2];

  printf("\n\n---Sum Matrix---\n");
  for(i=0;i<r;i++)
   {
    for(j=0;j<c;j++)
     printf("%d\t",sum[i][j]);
   }
 getch();

}






